SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Loop-level parallelism</title>

</head>

Loop-level parallelism

</h1>

</header>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr">Loop-level parallelism is a form of <a href="Parallelism_(computing)" class="mw-redirect" title="Parallelism (computing)">parallelism</a> in <a href="Software_programming" class="mw-redirect" title="Software programming">software programming</a> that is concerned with extracting parallel tasks from <a href="Control_flow#Loops" title="Control flow">loops</a>. The opportunity for loop-level parallelism often arises in computing programs where data is stored in <a href="Random_access" title="Random access">random access</a> <a href="Data_structures" class="mw-redirect" title="Data structures">data structures</a>. Where a sequential program will iterate over the data structure and operate on indices one at a time, a program exploiting loop-level parallelism will use multiple <a href="Thread_(computing)" title="Thread (computing)">threads</a> or <a href="Process_(computing)" title="Process (computing)">processes</a> which operate on some or all of the indices at the same time. Such parallelism provides a <a href="Speedup" title="Speedup">speedup</a> to overall execution time of the program, typically in line with <a href="Amdahl's_law" title="Amdahl's law">Amdahl's law</a>.

<div class="mw-heading mw-heading2"><h2 id="Description">Description</h2></div>

For simple loops, where each iteration is independent of the others, loop-level parallelism can be <a href="Embarrassingly_parallel" title="Embarrassingly parallel">embarrassingly parallel</a>, as parallelizing only requires assigning a process to handle each iteration. However, many algorithms are designed to run sequentially, and fail when parallel processes <a href="Race_condition" title="Race condition">race</a> due to dependence within the code. Sequential algorithms are sometimes applicable to parallel contexts with slight modification. Usually, though, they require <a href="Synchronization_(computer_science)" title="Synchronization (computer science)">process synchronization</a>. Synchronization can be either implicit, via <a href="Message_passing" title="Message passing">message passing</a>, or explicit, via synchronization primitives like <a href="Semaphore_(programming)" title="Semaphore (programming)">semaphores</a>.

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

Consider the following code operating on a list <code>L</code> of length <code>n</code>.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>for (int i = 0; i < n; ++i) {

S1: L[i] += 10;

}

</pre></div>

Each iteration of the loop takes the value from the current index of <code>L</code>, and increments it by 10. If statement <code>S1</code> takes <code>T</code> time to execute, then the loop takes time <code>n * T</code> to execute sequentially, ignoring time taken by loop constructs. Now, consider a system with <code>p</code> processors where <code>p > n</code>. If <code>n</code> threads run in parallel, the time to execute all <code>n</code> steps is reduced to <code>T</code>.

Less simple cases produce inconsistent, i.e. <a href="Serializability" class="mw-redirect" title="Serializability">non-serializable</a> outcomes. Consider the following loop operating on the same list <code>L</code>.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>for (int i = 1; i < n; ++i) {

S1: L[i] = L[i-1] + 10;

}

</pre></div>

Each iteration sets the current index to be the value of the previous plus ten. When run sequentially, each iteration is guaranteed that the previous iteration will already have the correct value. With multiple threads, <a href="Process_scheduling" class="mw-redirect" title="Process scheduling">process scheduling</a> and other considerations prevent the execution order from guaranteeing an iteration will execute only after its dependence is met. It very well may happen before, leading to unexpected results. Serializability can be restored by adding synchronization to preserve the dependence on previous iterations.

<div class="mw-heading mw-heading2"><h2 id="Dependencies_in_code">Dependencies in code</h2></div>

There are several types of dependences that can be found within code.<a href="#cite_note-Solihin-1">[1]</a><a href="#cite_note-2">[2]</a>

<th>Type

</th>

<th>Notation

</th>

<th>Description

</th></tr>

<tr>

<td>True (Flow) Dependence

</td>

</td>

<td>A true dependence between S1 and S2 means that S1 writes to a location later read from by S2

</td></tr>

<tr>

<td>Anti Dependence

</td>

</td>

<td>An anti-dependence between S1 and S2 means that S1 reads from a location later written to by S2.

</td></tr>

<tr>

<td>Output Dependence

</td>

</td>

<td>An output dependence between S1 and S2 means that S1 and S2 write to the same location.

</td></tr>

<tr>

<td>Input Dependence

</td>

</td>

<td>An input dependence between S1 and S2 means that S1 and S2 read from the same location.

</td></tr></tbody></table>

In order to preserve the sequential behaviour of a loop when run in parallel, True Dependence must be preserved. Anti-Dependence and Output Dependence can be dealt with by giving each process its own copy of variables (known as privatization).<a href="#cite_note-Solihin-1">[1]</a>

<div class="mw-heading mw-heading3"><h3 id="Example_of_true_dependence">Example of true dependence</h3></div>

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>S1: int a, b;

S2: a = 2;

S3: b = a + 40;

</pre></div>

<code>S2 ->T S3</code>, meaning that S2 has a true dependence on S3 because S2 writes to the variable <code>a</code>, which S3 reads from.

<div class="mw-heading mw-heading3"><h3 id="Example_of_anti-dependence">Example of anti-dependence</h3></div>

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>S1: int a, b = 40;

S2: a = b - 38;

S3: b = -1;

</pre></div>

<code>S2 ->A S3</code>, meaning that S2 has an anti-dependence on S3 because S2 reads from the variable <code>b</code> before S3 writes to it.

<div class="mw-heading mw-heading3"><h3 id="Example_of_output-dependence">Example of output-dependence</h3></div>

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>S1: int a, b = 40;

S2: a = b - 38;

S3: a = 2;

</pre></div>

<code>S2 ->O S3</code>, meaning that S2 has an output dependence on S3 because both write to the variable <code>a</code>.

<div class="mw-heading mw-heading3"><h3 id="Example_of_input-dependence">Example of input-dependence</h3></div>

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>S1: int a, b, c = 2;

S2: a = c - 1;

S3: b = c + 1;

</pre></div>

<code>S2 ->I S3</code>, meaning that S2 has an input dependence on S3 because S2 and S3 both read from variable <code>c</code>.

<div class="mw-heading mw-heading2"><h2 id="Dependence_in_loops">Dependence in loops</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Loop-carried_vs_loop-independent_dependence">Loop-carried vs loop-independent dependence</h3></div>

Loops can have two types of dependence:

<ul><li>Loop-carried dependence</li>

<li>Loop-independent dependence</li></ul>

In loop-independent dependence, loops have inter-iteration dependence, but do not have dependence between iterations. Each iteration may be treated as a block and performed in parallel without other synchronization efforts.

In the following example code used for swapping the values of two array of length n, there is a loop-independent dependence of <code>S1 ->T S3</code>.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>for (int i = 1; i < n; ++i) {

S1: tmp = a[i];

S2: a[i] = b[i];

S3: b[i] = tmp;

}

</pre></div>

In loop-carried dependence, statements in an iteration of a loop depend on statements in another iteration of the loop. Loop-Carried Dependence uses a modified version of the dependence notation seen earlier.

Example of loop-carried dependence where <code>S1[i] ->T S1[i + 1]</code>, where <code>i</code> indicates the current iteration, and <code>i + 1</code> indicates the next iteration.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>for (int i = 1; i < n; ++i) {

S1: a[i] = a[i-1] + 1;

}

</pre></div>

<div class="mw-heading mw-heading3"><h3 id="Loop_carried_dependence_graph">Loop carried dependence graph</h3></div>

A Loop-carried dependence graph graphically shows the loop-carried dependencies between iterations. Each iteration is listed as a node on the graph, and directed edges show the true, anti, and output dependencies between each iteration.

<div class="mw-heading mw-heading2"><h2 id="Types">Types</h2></div>

There are a variety of methodologies for parallelizing loops.

<ul><li>DISTRIBUTED Loop</li>

<li>DOALL Parallelism</li>

<li>DOACROSS Parallelism</li>

<li>HELIX <a href="#cite_note-Parallelism_in_DOACROSS_Loops-3">[3]</a></li>

<li>DOPIPE Parallelism</li></ul>

Each implementation varies slightly in how threads synchronize, if at all. In addition, parallel tasks must somehow be mapped to a process. These tasks can either be allocated statically or dynamically. Research has shown that load-balancing can be better achieved through some dynamic allocation algorithms than when done statically.<a href="#cite_note-4">[4]</a>

The process of parallelizing a sequential program can be broken down into the following discrete steps.<a href="#cite_note-Solihin-1">[1]</a> Each concrete loop-parallelization below implicitly performs them.

<th>Type

</th>

<th>Description

</th></tr>

<tr>

<td>Decomposition

</td>

<td>The program is broken down into tasks, the smallest exploitable unit of concurrence.

</td></tr>

<tr>

<td>Assignment

</td>

<td>Tasks are assigned to processes.

</td></tr>

<tr>

<td>Orchestration

</td>

<td>Data access, communication, and synchronization of processes.

</td></tr>

<tr>

<td>Mapping

</td>

<td>Processes are bound to processors.

</td></tr></tbody></table>

<div class="mw-heading mw-heading3"><h3 id="DISTRIBUTED_loop">DISTRIBUTED loop</h3></div>

When a loop has a loop-carried dependence, one way to parallelize it is to distribute the loop into several different loops. Statements that are not dependent on each other are separated so that these distributed loops can be executed in parallel. For example, consider the following code.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>for (int i = 1; i < n; ++i) {

S1: a[i] = a[i-1] + b[i];

S2: c[i] += d[i];

}

</pre></div>

The loop has a loop carried dependence <code>S1[i] ->T S1[i+1]</code> but S2 and S1 do not have a loop-independent dependence so we can rewrite the code as follows.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>loop1: for (int i = 1; i < n; ++i) {

S1: a[i] = a[i-1] + b[i];

}

loop2: for (int i = 1; i < n; ++i) {

S2: c[i] += d[i];

}

</pre></div>

Note that now loop1 and loop2 can be executed in parallel. Instead of single instruction being performed in parallel on different data as in data level parallelism, here different loops perform different tasks on different data. Let's say the time of execution of S1 and S2 be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{S_{1}}}">

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{S_{1}}}</annotation>

</semantics>

</math><img src="./dd1a3a2efacd89442b6fbfb5d1873f4429867c6e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.429ex; height:2.843ex;" alt="{\displaystyle T_{S_{1}}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{S_{2}}}">

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{S_{2}}}</annotation>

</semantics>

</math><img src="./b9e06fd95750482f18508e89bbf7dd432c58e53b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.429ex; height:2.843ex;" alt="{\displaystyle T_{S_{2}}}" loading="lazy"> then the execution time for sequential form of above code is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n*(T_{S_{1}}+T_{S_{2}})}">

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n*(T_{S_{1}}+T_{S_{2}})}</annotation>

</semantics>

</math><img src="./0635826114eb37640f6ed9725180cf6516988b77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:15.097ex; height:3.009ex;" alt="{\displaystyle n*(T_{S_{1}}+T_{S_{2}})}" loading="lazy">, Now because we split the two statements and put them in two different loops, gives us an execution time of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n*T_{S_{1}}+T_{S_{2}}}">

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n*T_{S_{1}}+T_{S_{2}}}</annotation>

</semantics>

</math><img src="./78fe6654004e74df2bb44c74a1c550795acf3ec1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:13.288ex; height:2.843ex;" alt="{\displaystyle n*T_{S_{1}}+T_{S_{2}}}" loading="lazy">. We call this type of parallelism either function or task parallelism.

<div class="mw-heading mw-heading3"><h3 id="DOALL_parallelism">DOALL parallelism</h3></div>

DOALL parallelism exists when statements within a loop can be executed independently (situations where there is no loop-carried dependence).<a href="#cite_note-Solihin-1">[1]</a> For example, the following code does not read from the array <code>a</code>, and does not update the arrays <code>b, c</code>. No iterations have a dependence on any other iteration.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>for (int i = 0; i < n; ++i) {

S1: a[i] = b[i] + c[i];

}

</pre></div>

Let's say the time of one execution of S1 be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{S_{1}}}">

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{S_{1}}}</annotation>

</semantics>

</math><img src="./dd1a3a2efacd89442b6fbfb5d1873f4429867c6e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.429ex; height:2.843ex;" alt="{\displaystyle T_{S_{1}}}" loading="lazy"> then the execution time for sequential form of above code is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n*T_{S_{1}}}">

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n*T_{S_{1}}}</annotation>

</semantics>

</math><img src="./97d33ca0b4cbde11ea8f0711901d554cdcbcdd26.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.018ex; height:2.843ex;" alt="{\displaystyle n*T_{S_{1}}}" loading="lazy">, Now because DOALL Parallelism exists when all iterations are independent, speed-up may be achieved by executing all iterations in parallel which gives us an execution time of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{S_{1}}}">

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{S_{1}}}</annotation>

</semantics>

</math><img src="./dd1a3a2efacd89442b6fbfb5d1873f4429867c6e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.429ex; height:2.843ex;" alt="{\displaystyle T_{S_{1}}}" loading="lazy">, which is the time taken for one iteration in sequential execution.

The following example, using a simplified pseudo code, shows how a loop might be parallelized to execute each iteration independently.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>begin_parallelism();

for (int i = 0; i < n; ++i) {

S1: a[i] = b[i] + c[i];

end_parallelism();

}

block();

</pre></div>

<div class="mw-heading mw-heading3"><h3 id="DOACROSS_parallelism">DOACROSS parallelism</h3></div>

DOACROSS Parallelism exists where iterations of a loop are parallelized by extracting calculations that can be performed independently and running them simultaneously.<a href="#cite_note-5">[5]</a>

Synchronization exists to enforce loop-carried dependence.

Consider the following, synchronous loop with dependence <code>S1[i] ->T S1[i+1]</code>.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>for (int i = 1; i < n; ++i) {

a[i] = a[i-1] + b[i] + 1;

}

</pre></div>

Each loop iteration performs two actions

<ul><li>Calculate <code>a[i-1] + b[i] + 1</code></li>

<li>Assign the value to <code>a[i]</code></li></ul>

Calculating the value <code>a[i-1] + b[i] + 1</code>, and then performing the assignment can be decomposed into two lines(statements S1 and S2):

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>S1: int tmp = b[i] + 1;

S2: a[i] = a[i-1] + tmp;

</pre></div>

The first line, <code>int tmp = b[i] + 1;</code>, has no loop-carried dependence. The loop can then be parallelized by computing the temp value in parallel, and then synchronizing the assignment to <code>a[i]</code>.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>post(0);

for (int i = 1; i < n; ++i) {

S1: int tmp = b[i] + 1;

wait(i-1);

S2: a[i] = a[i-1] + tmp;

post(i);

}

</pre></div>

Let's say the time of execution of S1 and S2 be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{S_{1}}}">

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{S_{1}}}</annotation>

</semantics>

</math><img src="./dd1a3a2efacd89442b6fbfb5d1873f4429867c6e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.429ex; height:2.843ex;" alt="{\displaystyle T_{S_{1}}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{S_{2}}}">

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{S_{2}}}</annotation>

</semantics>

</math><img src="./b9e06fd95750482f18508e89bbf7dd432c58e53b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.429ex; height:2.843ex;" alt="{\displaystyle T_{S_{2}}}" loading="lazy"> then the execution time for sequential form of above code is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n*(T_{S_{1}}+T_{S_{2}})}">

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n*(T_{S_{1}}+T_{S_{2}})}</annotation>

</semantics>

</math><img src="./0635826114eb37640f6ed9725180cf6516988b77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:15.097ex; height:3.009ex;" alt="{\displaystyle n*(T_{S_{1}}+T_{S_{2}})}" loading="lazy">, Now because DOACROSS Parallelism exists, speed-up may be achieved by executing iterations in a pipelined fashion which gives us an execution time of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{S_{1}}+n*T_{S_{2}}}">

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{S_{1}}+n*T_{S_{2}}}</annotation>

</semantics>

</math><img src="./18ddaa61e714adeb5515973d3b993e1f5651a32e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:13.288ex; height:2.843ex;" alt="{\displaystyle T_{S_{1}}+n*T_{S_{2}}}" loading="lazy">.

<div class="mw-heading mw-heading3"><h3 id="DOPIPE_parallelism">DOPIPE parallelism</h3></div>

DOPIPE Parallelism implements pipelined parallelism for loop-carried dependence where a loop iteration is distributed over multiple, synchronized loops.<a href="#cite_note-Solihin-1">[1]</a> The goal of DOPIPE is to act like an assembly line, where one stage is started as soon as there is sufficient data available for it from the previous stage.<a href="#cite_note-6">[6]</a>

Consider the following, synchronous code with dependence <code>S1[i] ->T S1[i+1]</code>.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>for (int i = 1; i < n; ++i) {

S1: a[i] = a[i-1] + b[i];

S2: c[i] += a[i];

}

</pre></div>

S1 must be executed sequentially, but S2 has no loop-carried dependence. S2 could be executed in parallel using DOALL Parallelism after performing all calculations needed by S1 in series. However, the speedup is limited if this is done. A better approach is to parallelize such that the S2 corresponding to each S1 executes when said S1 is finished.

Implementing pipelined parallelism results in the following set of loops, where the second loop may execute for an index as soon as the first loop has finished its corresponding index.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>for (int i = 1; i < n; ++i) {

S1: a[i] = a[i-1] + b[i];

post(i);

}

for (int i = 1; i < n; i++) {

wait(i);

S2: c[i] += a[i];

}

</pre></div>

Let's say the time of execution of S1 and S2 be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{S_{1}}}">

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{S_{1}}}</annotation>

</semantics>

</math><img src="./dd1a3a2efacd89442b6fbfb5d1873f4429867c6e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.429ex; height:2.843ex;" alt="{\displaystyle T_{S_{1}}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T_{S_{2}}}">

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T_{S_{2}}}</annotation>

</semantics>

</math><img src="./b9e06fd95750482f18508e89bbf7dd432c58e53b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.429ex; height:2.843ex;" alt="{\displaystyle T_{S_{2}}}" loading="lazy"> then the execution time for sequential form of above code is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n*(T_{S_{1}}+T_{S_{2}})}">

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n*(T_{S_{1}}+T_{S_{2}})}</annotation>

</semantics>

</math><img src="./0635826114eb37640f6ed9725180cf6516988b77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:15.097ex; height:3.009ex;" alt="{\displaystyle n*(T_{S_{1}}+T_{S_{2}})}" loading="lazy">, Now because DOPIPE Parallelism exists, speed-up may be achieved by executing iterations in a pipelined fashion which gives us an execution time of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n*T_{S_{1}}+(n/p)*T_{S_{2}}}">

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mrow>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n*T_{S_{1}}+(n/p)*T_{S_{2}}}</annotation>

</semantics>

</math><img src="./3253b67bd95a795c339575b6771f2994aa3235fb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:21.018ex; height:3.009ex;" alt="{\displaystyle n*T_{S_{1}}+(n/p)*T_{S_{2}}}" loading="lazy">, where p is the number of processor in parallel.

<ul><li><a href="Data_parallelism" title="Data parallelism">Data parallelism</a></li>

<li><a href="DOACROSS_parallelism" title="DOACROSS parallelism">DOACROSS parallelism</a></li>

<li><a href="Task_parallelism" title="Task parallelism">Task parallelism</a></li>

<li>Parallelism using different types of memory models like <a href="Shared_memory" title="Shared memory">shared</a> and <a href="Distributed_memory" title="Distributed memory">distributed</a> and <a href="Message_Passing_Interface" title="Message Passing Interface">Message Passing</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFSolihin2016" class="citation book cs1">Solihin, Yan (2016). Fundamentals of Parallel Architecture. Boca Raton, FL: CRC Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4822-1118-4</bdi>.</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFGoff1991" class="citation book cs1">Goff, Gina (1991). "Practical dependence testing". Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation - PLDI '91. pp. 15–29. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F113445.113448">10.1145/113445.113448</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0897914287</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:2357293">2357293</a>.</cite>

</li>

<li id="cite_note-Parallelism_in_DOACROSS_Loops-3"><a href="#cite_ref-Parallelism_in_DOACROSS_Loops_3-0">^</a> <cite id="CITEREFMurphy" class="citation web cs1">Murphy, Niall. <a rel="nofollow" class="external text" href="https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-882.pdf">"Discovering and exploiting parallelism in DOACROSS loops"</a> (PDF). University of Cambridge. Retrieved 10 September 2016.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFKavi" class="citation journal cs1">Kavi, Krishna. <a rel="nofollow" class="external text" href="https://www.researchgate.net/publication/220662641">"Parallelization of DOALL and DOACROSS Loops-a Survey"</a>.</cite> <code class="cs1-code">{{cite journal}}</code>: Cite journal requires <code class="cs1-code">|journal=</code> (help)

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFUnnikrishnan2012" class="citation cs2">Unnikrishnan, Priya (2012), "A Practical Approach to DOACROSS Parallelization", Euro-Par 2012 Parallel Processing, Lecture Notes in Computer Science, vol. 7484, pp. 219–231, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-642-32820-6_23">10.1007/978-3-642-32820-6_23</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-642-32819-0</bdi>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:18571258">18571258</a></cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://software.intel.com/sites/default/files/m/a/a/7/d/6/12758-MC_Forum_Zangbinyu_dopipe.pdf">"DoPipe: An Effective Approach to Parallelize Simulation"</a> (PDF). Intel. Retrieved 13 September 2016.</cite>

</li>

</ol></div></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Parallel_computing346" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Parallel_computing346" style="font-size:114%;margin:0 4em"><a href="Parallel_computing" title="Parallel computing">Parallel computing</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Distributed_computing" title="Distributed computing">Distributed computing</a></li>

<li><a href="Parallel_computing" title="Parallel computing">Parallel computing</a></li>

<li><a href="Parallel_algorithm" title="Parallel algorithm">Parallel algorithm</a></li>

<li><a href="Massively_parallel" title="Massively parallel">Massively parallel</a></li>

<li><a href="Cloud_computing" title="Cloud computing">Cloud computing</a></li>

<li><a href="High-performance_computing" title="High-performance computing">High-performance computing</a></li>

<li><a href="Multiprocessing" title="Multiprocessing">Multiprocessing</a></li>

<li><a href="Manycore_processor" title="Manycore processor">Manycore processor</a></li>

<li><a href="General-purpose_computing_on_graphics_processing_units" title="General-purpose computing on graphics processing units">GPGPU</a></li>

<li><a href="Computer_network" title="Computer network">Computer network</a></li>

<li><a href="Systolic_array" title="Systolic array">Systolic array</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Levels</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Instruction-level_parallelism" title="Instruction-level parallelism">Instruction</a></li>

<li><a href="Task_parallelism" title="Task parallelism">Thread</a></li>

<li><a href="Memory-level_parallelism" title="Memory-level parallelism">Memory</a></li>

<li><a href="Pipeline_(computing)" title="Pipeline (computing)">Pipeline</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Multithreading_(computer_architecture)" title="Multithreading (computer architecture)">Multithreading</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Temporal_multithreading" title="Temporal multithreading">Temporal</a></li>

<li><a href="Simultaneous_multithreading" title="Simultaneous multithreading">Simultaneous</a> (SMT)</li>

<li><a href="Simultaneous_and_heterogeneous_multithreading" title="Simultaneous and heterogeneous multithreading">Simultaneous and heterogenous</a></li>

<li><a href="Speculative_multithreading" title="Speculative multithreading">Speculative</a> (SpMT)</li>

<li><a href="Preemption_(computing)" title="Preemption (computing)">Preemptive</a></li>

<li><a href="Computer_multitasking#Cooperative_multitasking" title="Computer multitasking">Cooperative</a></li>

<li><a href="Bulldozer_(microarchitecture)#Bulldozer_core" title="Bulldozer (microarchitecture)">Clustered multi-thread</a> (CMT)</li>

<li><a href="Hardware_scout" title="Hardware scout">Hardware scout</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Theory</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Parallel_RAM" title="Parallel RAM">PRAM model</a></li>

<li><a href="Parallel_external_memory" title="Parallel external memory">PEM model</a></li>

<li><a href="Analysis_of_parallel_algorithms" title="Analysis of parallel algorithms">Analysis of parallel algorithms</a></li>

<li><a href="Amdahl's_law" title="Amdahl's law">Amdahl's law</a></li>

<li><a href="Gustafson's_law" title="Gustafson's law">Gustafson's law</a></li>

<li><a href="Cost_efficiency" title="Cost efficiency">Cost efficiency</a></li>

<li><a href="Karp%E2%80%93Flatt_metric" title="Karp–Flatt metric">Karp–Flatt metric</a></li>

<li><a href="Parallel_slowdown" title="Parallel slowdown">Slowdown</a></li>

<li><a href="Speedup" title="Speedup">Speedup</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Elements</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Process_(computing)" title="Process (computing)">Process</a></li>

<li><a href="Thread_(computing)" title="Thread (computing)">Thread</a></li>

<li><a href="Fiber_(computer_science)" title="Fiber (computer science)">Fiber</a></li>

<li><a href="Instruction_window" title="Instruction window">Instruction window</a></li>

<li><a href="Array_(data_structure)" title="Array (data structure)">Array</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Coordination</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Multiprocessing" title="Multiprocessing">Multiprocessing</a></li>

<li><a href="Memory_coherence" title="Memory coherence">Memory coherence</a></li>

<li><a href="Cache_coherence" title="Cache coherence">Cache coherence</a></li>

<li><a href="Cache_invalidation" title="Cache invalidation">Cache invalidation</a></li>

<li><a href="Barrier_(computer_science)" title="Barrier (computer science)">Barrier</a></li>

<li><a href="Synchronization_(computer_science)" title="Synchronization (computer science)">Synchronization</a></li>

<li><a href="Application_checkpointing" title="Application checkpointing">Application checkpointing</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Computer_programming" title="Computer programming">Programming</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Stream_processing" title="Stream processing">Stream processing</a></li>

<li><a href="Dataflow_programming" title="Dataflow programming">Dataflow programming</a></li>

<li><a href="Parallel_programming_model" title="Parallel programming model">Models</a>

<ul><li><a href="Implicit_parallelism" title="Implicit parallelism">Implicit parallelism</a></li>

<li><a href="Explicit_parallelism" title="Explicit parallelism">Explicit parallelism</a></li>

<li><a href="Concurrency_(computer_science)" title="Concurrency (computer science)">Concurrency</a></li></ul></li>

<li><a href="Non-blocking_algorithm" title="Non-blocking algorithm">Non-blocking algorithm</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Computer_hardware" title="Computer hardware">Hardware</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Flynn's_taxonomy" title="Flynn's taxonomy">Flynn's taxonomy</a>

<ul><li><a href="Single_instruction%2C_multiple_threads" title="Single instruction, multiple threads">Array processing</a> (SIMT)</li>

<li><a href="Flynn's_taxonomy#Pipelined_processor" title="Flynn's taxonomy">Pipelined processing</a></li>

<li><a href="Flynn's_taxonomy#Associative_processor" title="Flynn's taxonomy">Associative processing</a></li></ul></li>

<li><a href="Dataflow_architecture" title="Dataflow architecture">Dataflow architecture</a></li>

<li><a href="Instruction_pipelining" title="Instruction pipelining">Pipelined processor</a></li>

<li><a href="Superscalar_processor" title="Superscalar processor">Superscalar processor</a></li>

<li><a href="Vector_processor" title="Vector processor">Vector processor</a></li>

<li><a href="Multiprocessing" title="Multiprocessing">Multiprocessor</a>

<ul><li><a href="Symmetric_multiprocessing" title="Symmetric multiprocessing">symmetric</a></li>

<li><a href="Asymmetric_multiprocessing" title="Asymmetric multiprocessing">asymmetric</a></li></ul></li>

<li><a href="Semiconductor_memory" title="Semiconductor memory">Memory</a>

<ul><li><a href="Shared_memory" title="Shared memory">shared</a></li>

<li><a href="Distributed_memory" title="Distributed memory">distributed</a></li>

<li><a href="Distributed_shared_memory" title="Distributed shared memory">distributed shared</a></li>

<li><a href="Massively_parallel" title="Massively parallel">Massively parallel</a> computer</li>

<li><a href="Computer_cluster" title="Computer cluster">Computer cluster</a>

<ul><li><a href="Beowulf_cluster" title="Beowulf cluster">Beowulf cluster</a></li></ul></li>

<li><a href="Grid_computing" title="Grid computing">Grid computer</a></li>

<li><a href="Hardware_acceleration" title="Hardware acceleration">Hardware acceleration</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="API" title="API">APIs</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Ateji_PX" title="Ateji PX">Ateji PX</a></li>

<li><a href="Boost_(C%2B%2B_libraries)" title="Boost (C++ libraries)">Boost</a></li>

<li><a href="Chapel_(programming_language)" title="Chapel (programming language)">Chapel</a></li>

<li><a href="Charm%2B%2B" title="Charm++">Charm++</a></li>

<li><a href="Coarray_Fortran" title="Coarray Fortran">Coarray Fortran</a></li>

<li><a href="Dryad_(programming)" title="Dryad (programming)">Dryad</a></li>

<li><a href="Global_Arrays" title="Global Arrays">Global Arrays</a></li>

<li><a href="GPUOpen" title="GPUOpen">GPUOpen</a></li>

<li><a href="OpenMP" title="OpenMP">OpenMP</a></li>

<li><a href="OpenCL" title="OpenCL">OpenCL</a></li>

<li><a href="OpenHMPP" title="OpenHMPP">OpenHMPP</a></li>

<li><a href="OpenACC" title="OpenACC">OpenACC</a></li>

<li><a href="Parallel_Extensions" title="Parallel Extensions">Parallel Extensions</a></li>

<li><a href="Pthreads" title="Pthreads">pthreads</a></li>

<li><a href="RaftLib" title="RaftLib">RaftLib</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Problems</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Automatic_parallelization" title="Automatic parallelization">Automatic parallelization</a></li>

<li><a href="Deadlock_(computer_science)" title="Deadlock (computer science)">Deadlock</a></li>

<li><a href="Deterministic_algorithm" title="Deterministic algorithm">Deterministic algorithm</a></li>

<li><a href="Embarrassingly_parallel" title="Embarrassingly parallel">Embarrassingly parallel</a></li>

<li><a href="Parallel_slowdown" title="Parallel slowdown">Parallel slowdown</a></li>

<li><a href="Race_condition" title="Race condition">Race condition</a></li>

<li><a href="Software_lockout" title="Software lockout">Software lockout</a></li>

<li><a href="Scalability" title="Scalability">Scalability</a></li>

<li><a href="Starvation_(computer_science)" title="Starvation (computer science)">Starvation</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li> Category: Parallel computing</li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-05-02" href="https://en.wikipedia.org/wiki/?title=Loop-level_parallelism&oldid=1221791335">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>